package jjn.carl.binary_tree;

import commons.BinaryTreeHelper;
import commons.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Jiang Jining
 * @since 2023-07-18 23:57
 */
public class LeetCode501 {
    
    private List<Integer> result;
    private int maxCount;
    private int curCount;
    private TreeNode pre;
    
    public int[] findMode(TreeNode root) {
        this.result = new ArrayList<>();
        traversal(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }
    
    private void traversal(TreeNode current) {
        if (current == null) {
            return;
        }
        traversal(current.left);
        if (result.isEmpty() && maxCount == 0) {
            result.add(current.val);
        }
        int curVal = current.val;
        if (pre == null || curVal != pre.val) {
            curCount = 1;
        } else {
            curCount++;
        }
        if (curCount > maxCount) {
            result = new ArrayList<>();
            result.add(curVal);
            maxCount = curCount;
        } else if (curCount == maxCount) {
            result.add(curVal);
        }
        pre = current;
        traversal(current.right);
    }
    
    public static void main(String[] args) {
        List<Integer> input = new ArrayList<>();
        input.add(1);
        input.add(null);
        input.addAll(List.of(2, 2));
        TreeNode root = BinaryTreeHelper.buildTree(input);
        int[] ints = new LeetCode501().findMode(root);
        System.out.println("Arrays.toString(ints) = " + Arrays.toString(ints));
    }
}
